1. Field of the Invention
This invention relates to node position determination in a network, especially a wireless sensor network and a semi-definite programming method.
2. Description of the Related Art
There has been an increase in the use of ad hoc wireless sensor networks for monitoring environmental information (temperature, pressure, mineral content, sound levels, light etc) across an entire physical space. Typical networks of this type consist of a large number of densely deployed sensor nodes which must gather local data and communicate with other nodes. The sensor data from these nodes are relevant only if we know what location they refer to. Therefore knowledge of the node positions becomes imperative. The use of Global Positioning System (GPS) is a very expensive solution to this requirement. Instead, techniques to estimate node positions are being developed that rely just on the measurements of distances between neighboring nodes. The distance information could be based on criterion like time of arrival, time-difference of arrival and received signal strength. Depending on the accuracy of these measurements, processor power and memory constraints at each of the nodes, there is some degree of error in the distance information. Furthermore, it is assumed that the positions of a few anchor nodes are known. The problem of finding the positions of all the nodes given a few anchor nodes and relative distance information between the nodes is called the position estimation or localization problem.
Position Estimation or Localization Problem
This position estimation may be expressed with the following equations. The trace of a given matrix A denoted by Trace (A), is the sum of the entries on the main diagonal of A. We use I, e and 0 to denote the identity matrix, the vector of all ones and the vector of all zeros, whose dimension will be clear in the context. The inner product of two vectors p and q is denoted by <p, q>. The 2-norm of a vector x denoted by ∥x∥ is defined by √{square root over (<x,x>)}. A positive semidefinite matrix X is represented by X≧0.
A great deal of research has been done on the topic of position estimation in ad-hoc networks. See for example: L. Doherty, L. E. Ghaoui, and S. J. Pister. Convex position estimation in wireless sensor networks. In IEEE Infocom, volume 3, pages 1655-1663, April 2001 (“Doherty et al.”); and D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. An empirical study of epidemic algorithms in large scale multiho wireless networks. Technical report, University of California, Los Angeles, 2002. Most techniques use distance or angle measurements from a fixed set of reference or anchor nodes; or employ a grid of beacon nodes with known positions
One closely related approach is described by Doherty et al. wherein the proximity constraints between nodes which are within ‘hearing distance’ of each other are modeled as convex constraints. Then a feasibility problem can be solved by efficient convex programming techniques. Suppose two nodes x1 and x2 are within radio range R of each other, the proximity constraint can be represented as a convex second order cone constraint of the form:∥(x1−x2)∥2≦R  (1)
This can be formulated as a matrix linear inequality:
                              [                                                                                          I                    2                                    ⁢                  R                                                                                                  x                    1                                    -                                      x                    2                                                                                                                                            (                                                                  x                        1                                            -                                              x                        2                                                              )                                    T                                                            R                                              ]                ≽        0                            (        2        )            
Alternatively, if the exact distance r1,2≦R is known, we could set the constraint∥(x1−x2)∥2≦r1,2  (3)
The second-order cone method for solving Euclidean metric problems can be also found in G. Xue and Y. Ye. An efficient algorithm for minimizing a sum of Euclidean norms with applications. SIAM Journal on Optimization., 7:1017-1036, 1997, where its superior polynomial complexity efficiency is presented, which is incorporated by reference herein.
However, this technique yields good results only if the anchor nodes are placed on the outer boundary, since the estimated positions of their convex optimization model all lay within the convex hull of the anchor nodes. So if the anchor nodes are placed to the interior of the network, the position estimation of the unknown nodes will also tend to be the interior, yielding highly inaccurate results. For example, with just 5 anchors in a random 200 node network, the estimation error is almost twice the radio range.
One may ask why not add, if r1,2 is known, another “bounding away” constraint∥(x1−x2)∥2≦r1,2  (4)These two constraints (Equation (3) and (4)) are much tighter and would yield more accurate results. The problem is that the latter is not a convex constraint, so that the efficient convex optimization techniques cannot apply.
Shang et al. (Y. Shang, W. Ruml, Y. Zhang, and M. P. J. Fromherz. Localization from mere connectivety. In Proceedings of the 4th ACM international symposium on Mobile Ad Hoc Networking & Computing, pages 201-212. ACM Press, 2003.) demonstrate the use of a data analysis technique called “multidimensional scaling” (MDS) in estimating positions of unknown nodes. Firstly, using basic connectivity or distance information, a rough estimate of relative node distances is made. Then MDS is used to obtain a relative map of the node positions. Finally an absolute map is obtained by using the known node positions. This technique works well with few anchors and reasonably high connectivity. For instance, for a connectivity level of 12 and 2% anchors, the error is about half of the radio range.
The techniques described above are predominantly centralized although distributed versions can be developed. The available distance information between all the nodes must be present on a single computer for these techniques to work. The distributed approach has the advantage that the techniques can be executed on the sensor nodes themselves thus removing the need to relay all the information to a central computer. Many techniques have been proposed that try to emphasize the ad-hoc nature of computation required in them.
Niculescu and Nath (D. Niculescu and B. Nath. Ad hoc positioning system (APS). In IEEE GLOBECOM (1), pages 2926-2931, 2001.) describe the “DV-Hop” approach which is quite effective in dense and regular topologies. The anchor nodes flood their position information to all the nodes in the network. Each node then estimates its own position by performing a triangulation to three or more anchors. For more irregular topologies however, the accuracy can deteriorate to the radio range.
Savarese et al. (C. Savarese, J. Rabay, and K. Langendoen. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In USENIX Technical Annual Conference, June 2002.) present a two-phase algorithm in which the start-up phase involves finding the rough positions of the nodes using a technique similar to the “DV-Hop” approach. The refinement phase improves the accuracy of the estimated positions by performing least squares triangulations using its own estimates and the estimates of the nodes in its own neighborhood. This method can accurately estimate points within one third of the radio range.
When the number of anchor nodes is high, the “iterative multiplication” technique proposed by Savvides et al. (A. Savvides, C.-C. Han, and M. B. Srivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. In Mobile Computing and Networking, pages 166-179, 2001.) yields good results. Nodes that are connected to three or more anchors compute their position by triangulation and upgrade themselves to anchor nodes. Now their position information can also be used by the other unknown nodes for their position estimation in the next iteration.
Although there are many ways to solve the position estimation problem in a sensor network as described above, these various ways still have many deficiencies. For example, some of these methods are either not scalable or not distributed. As the number of nodes in the network increases, it becomes increasingly difficult to find a solution. Also the communication overhead increases substantially. Another problem for some of these approaches is the accuracy in the estimation, as described above. In some situations, the errors can be as big as the radio range or more. A third problem is the lack of an indication of the accuracy of each position estimation. Without the knowledge of how accurate the position estimation is, the use of the resulting estimation is very limited.
It is desirable to have a new method, system or device to advance the relevant art. It is desirable to have a method, system or device that can solve the position estimation problem efficiently, in either small or large sensor network, and that can provide an indication of the accuracy of the solution.